package lc;

import ch2linkedlist.Chapter;
import ch2linkedlist.ListNode;

public class InsertionSortList {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
        	return null;
        }
        
    	ListNode curr = head.next;
    	while (curr != null) {
    		ListNode n = head;
    		while (n != curr) {
    			if (n.val > curr.val) {
    				int tmp = n.val;
    				n.val = curr.val;
    				curr.val = tmp;
    			}
    			n = n.next;
    		}
    		curr = curr.next;
    	}
    	return head;
    }

    public static void main(String ...strings) {
    	InsertionSortList sol = new InsertionSortList();
		ListNode head = Chapter.createSampleList(new int [] {3, 1, 4, 2});
		ListNode sortList = sol.insertionSortList(head);
		Chapter.print(sortList);
    }
}
